백준 17387번
오늘 풀어본 문제는 백준의 17387번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
2차원 좌표 평면 위의 두 선분 $L_1$, $L_2$ 가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.
$L_1$ 의 양 끝 점은 $(x_1, y_1)$, $(x_2, y_2)$, $L_2$ 의 양 끝 점은 $(x_3, y_3)$, $(x_4, y_4)$ 이다.
입력
첫째 줄에 $L_1$ 의 양 끝 점 $x_1, y_1, x_2, y_2$ 가, 둘째 줄에 $L_2$ 의 양 끝 점 $x_3, y_3, x_4, y_4$ 가 주어진다.
출력
$L_1$ 과 $L_2$ 가 교차하면 $1$, 아니면 $0$ 을 출력한다.
제한
- $-1,000,000 ≤ x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4 ≤ 1,000,000$
- $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$, $x_4$, $y_4$ 는 정수
- 선분의 길이는 $0$ 보다 크다.
풀이과정
이 문제는 내가 직접 만든 자료구조인 GeometricLine 이 정의된 geometric_line.hpp 헤더 파일을 include 하는 방식으로 해결하였다. 백준 사이트에 제출 할 때는 헤더파일의 코드를 복사하고 붙여넣은 뒤 제출하였다.
필요한 사람은 내 Github 레포지토리2 의 코드를 확인하면 된다.
1번째 시도
문제를 보고 선분 교차 판정법을 이용하여 풀 수 있는 문제라는 걸 알 수 있었다. (사실 문제 이름부터 선분 교차라고 써있기 했다.)
예전에 만들어두었던 GeometricLine 클래스를 활용하여 문제해결을 시도하였다. 이 클래스에서 선분 교차를 판정하는 방식은 각 점들의 위치 차이를 계산한 벡터들의 외적한 값들을 이용한다. 자세한 방법은 검색해보면 알 수 있을 것이다.
코드는 다음과 같이 작성하였다.
geometric_line.hpp
#ifndef __GEOMETRIC_LINE_HPP__
#define __GEOMETRIC_LINE_HPP__
#include <utility>
template <typename T>
class GeometricLine {
private:
std::pair<T, T> start;
std::pair<T, T> end;
public:
GeometricLine() : start(std::make_pair(0, 0)), end(std::make_pair(0, 0)) {}
GeometricLine(const std::pair<T, T>& start, const std::pair<T, T>& end) : start(start), end(end) {
if (this->start > this->end) {
swap(this->end, this->start);
}
}
GeometricLine& operator=(const GeometricLine& other) {
this->start.first = other.start.first;
this->start.second = other.start.second;
this->end.first = other.end.first;
this->end.second = other.end.second;
return *this;
}
T getCCW(const std::pair<T, T>& target) const {
return (end.first - start.first) * (target.second - start.second) - (end.second - start.second) * (target.first - start.first);
}
bool cross(const GeometricLine& target) {
const T ourCCW = this->getCCW(target.start) * this->getCCW(target.end);
const T theirCCW = target.getCCW(this->start) * target.getCCW(this->end);
if (ourCCW == 0 && theirCCW == 0) {
if (this->start > target.end || target.start > this->end) {
return false;
}
else {
return true;
}
}
else {
return (ourCCW <= 0 && theirCCW <= 0);
}
}
const std::pair<T, T>& getStart(void) const {
return start;
}
const std::pair<T, T>& getEnd(void) const {
return end;
}
};
#endif // !__GEOMETRIC_LINE_HPP__
main.cpp
#include <bits/stdc++.h>
#include "geometric_line.hpp"
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
pair<int, int> p1, p2, p3, p4;
cin >> p1.first >> p1.second >> p2.first >> p2.second;
cin >> p3.first >> p3.second >> p4.first >> p4.second;
GeometricLine<int> L1(p1, p2);
GeometricLine<int> L2(p3, p4);
if (L1.cross(L2)) {
cout << 1;
}
else {
cout << 0;
}
return 0;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
2번째 시도
틀린 이유로 추정한 것은, 계산 과정에서 오버플로가 발생한 것이었다. 그래서 int 자료형 대신에 long long int 를 사용하는 것을 시도하였다.
코드는 main.cpp 파일만 다음과 같이 수정하였다.
#include <bits/stdc++.h>
#include "geometric_line.hpp"
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
pair<long long int, long long int> p1, p2, p3, p4;
cin >> p1.first >> p1.second >> p2.first >> p2.second;
cin >> p3.first >> p3.second >> p4.first >> p4.second;
GeometricLine<long long int> L1(p1, p2);
GeometricLine<long long int> L2(p3, p4);
if (L1.cross(L2)) {
cout << 1;
}
else {
cout << 0;
}
return 0;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
3번째 시도
여전히 틀린 것이 이해가 가지 않아 게시판을 돌아다니며 문제점을 탐색한 결과, long long int 로도 여전히 오버플로가 발생한다는 것이 문제였다. 최후의 방법으로 더 큰 수를 다룰 수 있는 double 자료형을 사용해보았다.
코드는 다음과 같이 수정하였다. 헤더 파일의 내용은 그대로이고, main 함수의 내용만 바뀌었다.
#include <bits/stdc++.h>
#include "geometric_line.hpp"
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
pair<double, double> p1, p2, p3, p4;
cin >> p1.first >> p1.second >> p2.first >> p2.second;
cin >> p3.first >> p3.second >> p4.first >> p4.second;
GeometricLine<double> L1(p1, p2);
GeometricLine<double> L2(p3, p4);
if (L1.cross(L2)) {
cout << 1;
}
else {
cout << 0;
}
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
오버플로 문제가 나면 long long int 나 unsigned long long int 로 항상 해결이 되었는데, double 까지 써야했던 건 이번이 처음인 것 같다… PS는 매번 충격의 연속인 듯 하다…
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/17387
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/17387/geometric_line.hpp